package 中等.前缀和与差分;

/**
 * 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
 * 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表
 * 示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些
 * 位置是从汽车的初始位置向东的公里数。
 * 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
 *
 * @author xudongfu
 * @date 2023/12/02
 */
public class 拼车_1094 {

    public static void main(String[] args) {

        System.out.println(carPooling2(new int[][]{{2, 1, 5}, {3, 5, 7}}, 3));

    }

    /**
     * 模拟
     */
    public static boolean carPooling(int[][] trips, int capacity) {

        int[] record = new int[1001];
        for (int[] trip : trips) {
            for (int i = trip[1]; i < trip[2]; i++) {
                record[i] += trip[0];
                if (record[i] > capacity) {
                    return false;
                }
            }

        }

        return true;
    }

    /**
     * 差分数组
     * trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，
     * 接他们和放他们的位置分别是 fromi 和 toi，toi的位置是下车，不用计算人数，使用一个
     * 数组记录位置 i 同时需要搭载的人数，每个 trip[i] 代表需要在 [fromi,toi-1] 每个
     * 位置上增加人数 numPassengersi，一个范围内的 + 数 ，可以用差分数组记录
     */
    public static boolean carPooling2(int[][] trips, int capacity) {
        int[] diff = new int[1001];

        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }

        int curCnt = 0;
        for (int num : diff) {
            curCnt += num;
            if (curCnt > capacity) {
                return false;
            }
        }

        return true;
    }
}
